package com.cuz.hot100;

import java.util.Arrays;

public class Q34searchRange {

    public static void main(String[] args) {
        //[5,7,7,8,8,10]
        //6
        int[] ints = searchRange1(new int[]{1}, 0);
        System.out.println(Arrays.toString(ints));
    }

    public static int[] searchRange1(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        //第一次找到的值
        int first = -1;

        int left = -1;
        int right = nums.length;

        // 1 2 3 3 3 4 5    4
        while (left + 1 != right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                // 1           1
                if (mid == 0 || nums[mid - 1] < target) {
                    first = mid;
                    break;
                } else {
                    //
                    right = mid;
                }
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        //不存在   如果第一次没找到 不存在数组中
        if (first == -1) {
            return new int[]{-1, -1};
        }

        left = first;
        right = nums.length;
        //最后一次出现
        //1 2 3  2 （1 1）
        int last = -1;
        while (left + 1 != right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                if (mid == nums.length - 1 || nums[mid + 1] > target) {
                    last = mid;
                    break;
                } else {
                    left = mid;
                }
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return new int[]{first, last == -1 ? first : last};
    }

}
